<html>
 <head>
  <meta charset="utf-8"/>
  <meta content="width=device-width, initial-scale=1, maximum-scale=1, user-scalable=no" name="viewport"/>
  <title>
   中文分词算法 之 基于词典的逆向最大匹配算法  | 数螺 | NAUT IDEA
  </title>
  <link href="http://cdn.bootcss.com/bootstrap/3.3.6/css/bootstrap-theme.min.css" rel="stylesheet"/>
  <link href="http://cdn.bootcss.com/bootstrap/3.3.6/css/bootstrap.min.css" rel="stylesheet"/>
  <style type="text/css">
   #xmain img {
                  max-width: 100%;
                  display: block;
                  margin-top: 10px;
                  margin-bottom: 10px;
                }

                #xmain p {
                    line-height:150%;
                    font-size: 16px;
                    margin-top: 20px;
                }

                #xmain h2 {
                    font-size: 24px;
                }

                #xmain h3 {
                    font-size: 20px;
                }

                #xmain h4 {
                    font-size: 18px;
                }


                .header {
	           background-color: #0099ff;
	           color: #ffffff;
	           margin-bottom: 20px;
	        }

	        .header p {
                  margin: 0px;
                  padding: 10px 0;
                  display: inline-block;  
                  vertical-align: middle;
                  font-size: 16px;
               }

               .header a {
                 color: white;
               }

              .header img {
                 height: 25px;
              }
  </style>
  <script src="http://cdn.bootcss.com/jquery/3.0.0/jquery.min.js">
  </script>
  <script src="http://nautstatic-10007657.file.myqcloud.com/static/css/readability.min.js" type="text/javascript">
  </script>
  <script type="text/javascript">
   $(document).ready(function() {
                 var loc = document.location;
                 var uri = {
                  spec: "http://dataunion.org/16736.html",
                  host: "http://dataunion.org",
                  prePath: "http://dataunion.org",
                  scheme: "http",
                  pathBase: "http://dataunion.org/"
                 };
    
                 var documentClone = document.cloneNode(true);
                 var article = new Readability(uri, documentClone).parse();
     
                 document.getElementById("xmain").innerHTML = article.content;
                });
  </script>
  <!-- 1466461429: Accept with keywords: (title(0.142857142857):逆向,中文,数盟,词典,算法,社区,分词, topn(0.2):逆向,社区,初始化,数盟,活象,查找,内存,行数,长度,切词,文件,词典,未找到,文章,拷贝,数目,中文,性能,重置,乒乓球拍,算法,词数,词长,优化,分词,字符,代码,耗时,作者,文本).-->
 </head>
 <body onload="">
  <div class="header">
   <div class="container">
    <div class="row">
     <div class="col-xs-6 col-sm-6 text-left">
      <a href="/databee">
       <img src="http://nautidea-10007657.cos.myqcloud.com/logo_white.png"/>
      </a>
      <a href="/databee">
       <p>
        数螺
       </p>
      </a>
     </div>
     <div class="hidden-xs col-sm-6 text-right">
      <p>
       致力于数据科学的推广和知识传播
      </p>
     </div>
    </div>
   </div>
  </div>
  <div class="container text-center">
   <h1>
    中文分词算法 之 基于词典的逆向最大匹配算法
   </h1>
  </div>
  <div class="container" id="xmain">
   ﻿﻿
   <title>
    中文分词算法 之 基于词典的逆向最大匹配算法 | 数盟社区
   </title>
   <!-- All in One SEO Pack 2.2.7.6.2 by Michael Torbert of Semper Fi Web Design[32,69] -->
   <!-- /all in one seo pack -->
   <!--
<div align="center">
<a href="http://strata.oreilly.com.cn/hadoop-big-data-cn?cmp=mp-data-confreg-home-stcn16_dataunion_pc" target="_blank"><img src="http://dataunion.org/wp-content/uploads/2016/05/stratabj.jpg"/ ></a>
</div>
-->
   <header id="header-web">
    <div class="header-main">
     <hgroup class="logo">
      <h1>
       <a href="http://dataunion.org/" rel="home" title="数盟社区">
        <img src="http://dataunion.org/wp-content/themes/yzipi/images/logo.png"/>
       </a>
      </h1>
     </hgroup>
     <!--logo-->
     <nav class="header-nav">
      <ul class="menu" id="menu-%e4%b8%bb%e8%8f%9c%e5%8d%95">
       <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-has-children menu-item-71" id="menu-item-71">
        <a href="http://dataunion.org/category/events" title="events">
         活动
        </a>
        <ul class="sub-menu">
         <li class="menu-item menu-item-type-post_type menu-item-object-page menu-item-22457" id="menu-item-22457">
          <a href="http://dataunion.org/2016timeline">
           2016档期
          </a>
         </li>
         <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-22459" id="menu-item-22459">
          <a href="http://dataunion.org/category/parterc">
           合作会议
          </a>
         </li>
        </ul>
       </li>
       <li class="menu-item menu-item-type-taxonomy menu-item-object-category current-post-ancestor current-menu-parent current-post-parent menu-item-has-children menu-item-20869" id="menu-item-20869">
        <a href="http://dataunion.org/category/tech" title="articles">
         文章
        </a>
        <ul class="sub-menu">
         <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-20867" id="menu-item-20867">
          <a href="http://dataunion.org/category/tech/base" title="base">
           基础架构
          </a>
         </li>
         <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3302" id="menu-item-3302">
          <a href="http://dataunion.org/category/tech/ai" title="ai">
           人工智能
          </a>
         </li>
         <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3303" id="menu-item-3303">
          <a href="http://dataunion.org/category/tech/analysis" title="analysis">
           数据分析
          </a>
         </li>
         <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-21920" id="menu-item-21920">
          <a href="http://dataunion.org/category/tech/dm">
           数据挖掘
          </a>
         </li>
         <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3314" id="menu-item-3314">
          <a href="http://dataunion.org/category/tech/viz" title="viz">
           可视化
          </a>
         </li>
         <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-3305" id="menu-item-3305">
          <a href="http://dataunion.org/category/tech/devl" title="devl">
           编程语言
          </a>
         </li>
        </ul>
       </li>
       <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-has-children menu-item-20876" id="menu-item-20876">
        <a href="http://dataunion.org/category/industry">
         行业
        </a>
        <ul class="sub-menu">
         <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-16328" id="menu-item-16328">
          <a href="http://dataunion.org/category/industry/case" title="case">
           行业应用
          </a>
         </li>
         <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-2112" id="menu-item-2112">
          <a href="http://dataunion.org/category/industry/demo" title="demo">
           Demo展示
          </a>
         </li>
         <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-21562" id="menu-item-21562">
          <a href="http://dataunion.org/category/industry/news">
           行业资讯
          </a>
         </li>
        </ul>
       </li>
       <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-311" id="menu-item-311">
        <a href="http://dataunion.org/category/sources" title="sources">
         资源
        </a>
       </li>
       <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-20870" id="menu-item-20870">
        <a href="http://dataunion.org/category/books" title="book">
         图书
        </a>
       </li>
       <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-21363" id="menu-item-21363">
        <a href="http://dataunion.org/category/training">
         课程
        </a>
       </li>
       <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-has-children menu-item-21853" id="menu-item-21853">
        <a href="http://dataunion.org/category/jobs">
         职位
        </a>
        <ul class="sub-menu">
         <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-22050" id="menu-item-22050">
          <a href="http://dataunion.org/category/career">
           职业规划
          </a>
         </li>
        </ul>
       </li>
      </ul>
     </nav>
     <!--header-nav-->
    </div>
   </header>
   <!--header-web-->
   <div id="main">
    <div id="soutab">
     <form action="http://dataunion.org/" class="search" method="get">
     </form>
    </div>
    <div id="container">
     <nav id="mbx">
      当前位置：
      <a href="http://dataunion.org">
       首页
      </a>
      &gt;
      <a href="http://dataunion.org/category/tech">
       文章
      </a>
      &gt;  正文
     </nav>
     <!--mbx-->
     <article class="content">
      <header align="centre" class="contenttitle">
       <div class="mscc">
        <h1 class="mscctitle">
         <a href="http://dataunion.org/16736.html">
          中文分词算法 之 基于词典的逆向最大匹配算法
         </a>
        </h1>
        <address class="msccaddress ">
         <em>
          1,435 次阅读 -
         </em>
         <a href="http://dataunion.org/category/tech" rel="category tag">
          文章
         </a>
        </address>
       </div>
      </header>
      <div class="content-text">
       <p>
        在之前的博文中介绍了
        <a href="http://dataunion.org/16370.html">
         基于词典的正向最大匹配算法
        </a>
        ，用了不到50行代码就实现了，然后分析了词典查找算法的时空复杂性，最后使用前缀树来实现词典查找算法，并做了3次优化。
       </p>
       <p>
       </p>
       <p>
        下面我们看看基于词典的逆向最大匹配算法的实现，实验表明，对于汉语来说，逆向最大匹配算法比(正向)最大匹配算法更有效，如下代码所示：
       </p>
       <p>
       </p>
       <div class="dp-highlighter" id="">
        <div class="bar">
         <div class="tools">
          Java代码
         </div>
        </div>
        <ol class="dp-j" start="1">
         <li>
          <span class="keyword">
           public
          </span>
          <span class="keyword">
           static
          </span>
          List&lt;String&gt; segReverse(String text){
         </li>
         <li>
          Stack&lt;String&gt; result =
          <span class="keyword">
           new
          </span>
          Stack&lt;&gt;();
         </li>
         <li>
          <span class="keyword">
           while
          </span>
          (text.length()&gt;
          <span class="number">
           0
          </span>
          ){
         </li>
         <li>
          <span class="keyword">
           int
          </span>
          len=MAX_LENGTH;
         </li>
         <li>
          <span class="keyword">
           if
          </span>
          (text.length()&lt;len){
         </li>
         <li>
          len=text.length();
         </li>
         <li>
          }
         </li>
         <li>
          <span class="comment">
           //取指定的最大长度的文本去词典里面匹配
          </span>
         </li>
         <li>
          String tryWord = text.substring(text.length() – len);
         </li>
         <li>
          <span class="keyword">
           while
          </span>
          (!DIC.contains(tryWord)){
         </li>
         <li>
          <span class="comment">
           //如果长度为一且在词典中未找到匹配，则按长度为一切分
          </span>
         </li>
         <li>
          <span class="keyword">
           if
          </span>
          (tryWord.length()==
          <span class="number">
           1
          </span>
          ){
         </li>
         <li>
          <span class="keyword">
           break
          </span>
          ;
         </li>
         <li>
          }
         </li>
         <li>
          <span class="comment">
           //如果匹配不到，则长度减一继续匹配
          </span>
         </li>
         <li>
          tryWord=tryWord.substring(
          <span class="number">
           1
          </span>
          );
         </li>
         <li>
          }
         </li>
         <li>
          result.push(tryWord);
         </li>
         <li>
          <span class="comment">
           //从待分词文本中去除已经分词的文本
          </span>
         </li>
         <li>
          text=text.substring(
          <span class="number">
           0
          </span>
          , text.length()-tryWord.length());
         </li>
         <li>
          }
         </li>
         <li>
          <span class="keyword">
           int
          </span>
          len=result.size();
         </li>
         <li>
          List&lt;String&gt; list =
          <span class="keyword">
           new
          </span>
          ArrayList&lt;&gt;(len);
         </li>
         <li>
          <span class="keyword">
           for
          </span>
          (
          <span class="keyword">
           int
          </span>
          i=
          <span class="number">
           0
          </span>
          ;i&lt;len;i++){
         </li>
         <li>
          list.add(result.pop());
         </li>
         <li>
          }
         </li>
         <li>
          <span class="keyword">
           return
          </span>
          list;
         </li>
         <li>
          }
         </li>
        </ol>
       </div>
       <p>
       </p>
       <p>
        算法跟正向相差不大，重点是使用Stack来存储分词结果，具体差异如下图所示：
        <br/>
        <img src="http://dataunion.org/wp-content/uploads/2015/05/4d239aff-03a5-38ec-b578-7446a4f64049.png"/>
        <br/>
        下面看看正向和逆向的分词效果，使用如下代码：
       </p>
       <p>
       </p>
       <div class="dp-highlighter" id="">
        <div class="bar">
         <div class="tools">
          Java代码
         </div>
        </div>
        <ol class="dp-j" start="1">
         <li>
          <span class="keyword">
           public
          </span>
          <span class="keyword">
           static
          </span>
          <span class="keyword">
           void
          </span>
          main(String[] args){
         </li>
         <li>
          List&lt;String&gt; sentences =
          <span class="keyword">
           new
          </span>
          ArrayList&lt;&gt;();
         </li>
         <li>
          sentences.add(
          <span class="string">
           “杨尚川是APDPlat应用级产品开发平台的作者”
          </span>
          );
         </li>
         <li>
          sentences.add(
          <span class="string">
           “研究生命的起源”
          </span>
          );
         </li>
         <li>
          sentences.add(
          <span class="string">
           “长春市长春节致辞”
          </span>
          );
         </li>
         <li>
          sentences.add(
          <span class="string">
           “他从马上下来”
          </span>
          );
         </li>
         <li>
          sentences.add(
          <span class="string">
           “乒乓球拍卖完了”
          </span>
          );
         </li>
         <li>
          sentences.add(
          <span class="string">
           “咬死猎人的狗”
          </span>
          );
         </li>
         <li>
          sentences.add(
          <span class="string">
           “大学生活象白纸”
          </span>
          );
         </li>
         <li>
          sentences.add(
          <span class="string">
           “他有各种才能”
          </span>
          );
         </li>
         <li>
          sentences.add(
          <span class="string">
           “有意见分歧”
          </span>
          );
         </li>
         <li>
          <span class="keyword">
           for
          </span>
          (String sentence : sentences){
         </li>
         <li>
          System.out.println(
          <span class="string">
           “正向最大匹配: “
          </span>
          +seg(sentence));
         </li>
         <li>
          System.out.println(
          <span class="string">
           “逆向最大匹配: “
          </span>
          +segReverse(sentence));
         </li>
         <li>
          }
         </li>
         <li>
          }
         </li>
        </ol>
       </div>
       <p>
       </p>
       <p>
        运行结果如下：
       </p>
       <p>
       </p>
       <div class="dp-highlighter" id="">
        <div class="bar">
         <div class="tools">
          Java代码
         </div>
        </div>
        <ol class="dp-j" start="1">
         <li>
          开始初始化词典
         </li>
         <li>
          完成初始化词典，词数目：
          <span class="number">
           427452
          </span>
         </li>
         <li>
          最大分词长度：
          <span class="number">
           16
          </span>
         </li>
         <li>
          正向最大匹配: [杨尚川, 是, APDPlat, 应用, 级, 产品开发, 平台, 的, 作者]
         </li>
         <li>
          逆向最大匹配: [杨尚川, 是, APDPlat, 应用, 级, 产品开发, 平台, 的, 作者]
         </li>
         <li>
          正向最大匹配: [研究生, 命, 的, 起源]
         </li>
         <li>
          逆向最大匹配: [研究, 生命, 的, 起源]
         </li>
         <li>
          正向最大匹配: [长春市, 长春, 节, 致辞]
         </li>
         <li>
          逆向最大匹配: [长春, 市长, 春节, 致辞]
         </li>
         <li>
          正向最大匹配: [他, 从, 马上, 下来]
         </li>
         <li>
          逆向最大匹配: [他, 从, 马上, 下来]
         </li>
         <li>
          正向最大匹配: [乒乓球拍, 卖完, 了]
         </li>
         <li>
          逆向最大匹配: [乒乓球拍, 卖完, 了]
         </li>
         <li>
          正向最大匹配: [咬, 死, 猎人, 的, 狗]
         </li>
         <li>
          逆向最大匹配: [咬, 死, 猎人, 的, 狗]
         </li>
         <li>
          正向最大匹配: [大学生, 活象, 白纸]
         </li>
         <li>
          逆向最大匹配: [大学生, 活象, 白纸]
         </li>
         <li>
          正向最大匹配: [他, 有, 各种, 才能]
         </li>
         <li>
          逆向最大匹配: [他, 有, 各种, 才能]
         </li>
         <li>
          正向最大匹配: [有意, 见, 分歧]
         </li>
         <li>
          逆向最大匹配: [有, 意见分歧]
         </li>
        </ol>
       </div>
       <p>
       </p>
       <p>
        下面看看实际的分词性能如何，对输入文件进行分词，然后将分词结果保存到输出文件，输入文本文件从这里
        <a href="http://pan.baidu.com/s/1qW34H1U" target="_blank" title="http://pan.baidu.com/s/1qW34H1U">
         下载
        </a>
        ，解压后大小为69M，词典文件从这里
        <a href="http://pan.baidu.com/s/1i37gKLZ" target="_blank" title="http://pan.baidu.com/s/1i37gKLZ">
         下载
        </a>
        ，解压后大小为4.5M，项目
        <a href="https://github.com/ysc/word" target="_blank" title="https://github.com/ysc/word">
         源代码
        </a>
        托管在GITHUB：
       </p>
       <p>
       </p>
       <div class="dp-highlighter" id="">
        <div class="bar">
         <div class="tools">
          Java代码
         </div>
        </div>
        <ol class="dp-j" start="1">
         <li>
          <span class="comment">
           /**
          </span>
         </li>
         <li>
          <span class="comment">
           * 将一个文件分词后保存到另一个文件
          </span>
         </li>
         <li>
          <span class="comment">
           * @author 杨尚川
          </span>
         </li>
         <li>
          <span class="comment">
           */
          </span>
         </li>
         <li>
          <span class="keyword">
           public
          </span>
          <span class="keyword">
           class
          </span>
          SegFile {
         </li>
         <li>
          <span class="keyword">
           public
          </span>
          <span class="keyword">
           static
          </span>
          <span class="keyword">
           void
          </span>
          main(String[] args)
          <span class="keyword">
           throws
          </span>
          Exception{
         </li>
         <li>
          String input =
          <span class="string">
           “input.txt”
          </span>
          ;
         </li>
         <li>
          String output =
          <span class="string">
           “output.txt”
          </span>
          ;
         </li>
         <li>
          <span class="keyword">
           if
          </span>
          (args.length ==
          <span class="number">
           2
          </span>
          ){
         </li>
         <li>
          input = args[
          <span class="number">
           0
          </span>
          ];
         </li>
         <li>
          output = args[
          <span class="number">
           1
          </span>
          ];
         </li>
         <li>
          }
         </li>
         <li>
          <span class="keyword">
           long
          </span>
          start = System.currentTimeMillis();
         </li>
         <li>
          segFile(input, output);
         </li>
         <li>
          <span class="keyword">
           long
          </span>
          cost = System.currentTimeMillis()-start;
         </li>
         <li>
          System.out.println(
          <span class="string">
           “cost time:”
          </span>
          +cost+
          <span class="string">
           ” ms”
          </span>
          );
         </li>
         <li>
          }
         </li>
         <li>
          <span class="keyword">
           public
          </span>
          <span class="keyword">
           static
          </span>
          <span class="keyword">
           void
          </span>
          segFile(String input, String output)
          <span class="keyword">
           throws
          </span>
          Exception{
         </li>
         <li>
          <span class="keyword">
           float
          </span>
          max=(
          <span class="keyword">
           float
          </span>
          )Runtime.getRuntime().maxMemory()/
          <span class="number">
           1000000
          </span>
          ;
         </li>
         <li>
          <span class="keyword">
           float
          </span>
          total=(
          <span class="keyword">
           float
          </span>
          )Runtime.getRuntime().totalMemory()/
          <span class="number">
           1000000
          </span>
          ;
         </li>
         <li>
          <span class="keyword">
           float
          </span>
          free=(
          <span class="keyword">
           float
          </span>
          )Runtime.getRuntime().freeMemory()/
          <span class="number">
           1000000
          </span>
          ;
         </li>
         <li>
          String pre=
          <span class="string">
           “执行之前剩余内存:”
          </span>
          +max+
          <span class="string">
           “-“
          </span>
          +total+
          <span class="string">
           “+”
          </span>
          +free+
          <span class="string">
           “=”
          </span>
          +(max-total+free);
         </li>
         <li>
          <span class="keyword">
           try
          </span>
          (BufferedReader reader =
          <span class="keyword">
           new
          </span>
          BufferedReader(
          <span class="keyword">
           new
          </span>
          InputStreamReader(
          <span class="keyword">
           new
          </span>
          FileInputStream(input),
          <span class="string">
           “utf-8”
          </span>
          ));
         </li>
         <li>
          BufferedWriter writer =
          <span class="keyword">
           new
          </span>
          BufferedWriter(
          <span class="keyword">
           new
          </span>
          OutputStreamWriter(
          <span class="keyword">
           new
          </span>
          FileOutputStream(output),
          <span class="string">
           “utf-8”
          </span>
          ))){
         </li>
         <li>
          <span class="keyword">
           int
          </span>
          textLength=
          <span class="number">
           0
          </span>
          ;
         </li>
         <li>
          <span class="keyword">
           long
          </span>
          start = System.currentTimeMillis();
         </li>
         <li>
          String line = reader.readLine();
         </li>
         <li>
          <span class="keyword">
           while
          </span>
          (line !=
          <span class="keyword">
           null
          </span>
          ){
         </li>
         <li>
          textLength += line.length();
         </li>
         <li>
          writer.write(WordSeg.seg(line).toString()+
          <span class="string">
           “\n”
          </span>
          );
         </li>
         <li>
          line = reader.readLine();
         </li>
         <li>
          }
         </li>
         <li>
          <span class="keyword">
           long
          </span>
          cost = System.currentTimeMillis() – start;
         </li>
         <li>
          <span class="keyword">
           float
          </span>
          rate = textLength/cost;
         </li>
         <li>
          System.out.println(
          <span class="string">
           “文本字符：”
          </span>
          +textLength);
         </li>
         <li>
          System.out.println(
          <span class="string">
           “分词耗时：”
          </span>
          +cost+
          <span class="string">
           ” 毫秒”
          </span>
          );
         </li>
         <li>
          System.out.println(
          <span class="string">
           “分词速度：”
          </span>
          +rate+
          <span class="string">
           ” 字符/毫秒”
          </span>
          );
         </li>
         <li>
          }
         </li>
         <li>
          max=(
          <span class="keyword">
           float
          </span>
          )Runtime.getRuntime().maxMemory()/
          <span class="number">
           1000000
          </span>
          ;
         </li>
         <li>
          total=(
          <span class="keyword">
           float
          </span>
          )Runtime.getRuntime().totalMemory()/
          <span class="number">
           1000000
          </span>
          ;
         </li>
         <li>
          free=(
          <span class="keyword">
           float
          </span>
          )Runtime.getRuntime().freeMemory()/
          <span class="number">
           1000000
          </span>
          ;
         </li>
         <li>
          String post=
          <span class="string">
           “执行之后剩余内存:”
          </span>
          +max+
          <span class="string">
           “-“
          </span>
          +total+
          <span class="string">
           “+”
          </span>
          +free+
          <span class="string">
           “=”
          </span>
          +(max-total+free);
         </li>
         <li>
          System.out.println(pre);
         </li>
         <li>
          System.out.println(post);
         </li>
         <li>
          }
         </li>
         <li>
          }
         </li>
        </ol>
       </div>
       <p>
       </p>
       <p>
        测试结果如下（对比TrieV3和HashSet的表现）：
       </p>
       <p>
       </p>
       <div class="dp-highlighter" id="">
        <div class="bar">
         <div class="tools">
          Java代码
         </div>
        </div>
        <ol class="dp-j" start="1">
         <li>
          开始初始化词典
         </li>
         <li>
          dic.
          <span class="keyword">
           class
          </span>
          =org.apdplat.word.dictionary.impl.TrieV3
         </li>
         <li>
          dic.path=dic.txt
         </li>
         <li>
          完成初始化词典，耗时
          <span class="number">
           695
          </span>
          毫秒，词数目：
          <span class="number">
           427452
          </span>
         </li>
         <li>
          词典最大词长：
          <span class="number">
           16
          </span>
         </li>
         <li>
          词长
          <span class="number">
           0
          </span>
          的词数为：
          <span class="number">
           1
          </span>
         </li>
         <li>
          词长
          <span class="number">
           1
          </span>
          的词数为：
          <span class="number">
           11581
          </span>
         </li>
         <li>
          词长
          <span class="number">
           2
          </span>
          的词数为：
          <span class="number">
           146497
          </span>
         </li>
         <li>
          词长
          <span class="number">
           3
          </span>
          的词数为：
          <span class="number">
           162776
          </span>
         </li>
         <li>
          词长
          <span class="number">
           4
          </span>
          的词数为：
          <span class="number">
           90855
          </span>
         </li>
         <li>
          词长
          <span class="number">
           5
          </span>
          的词数为：
          <span class="number">
           6132
          </span>
         </li>
         <li>
          词长
          <span class="number">
           6
          </span>
          的词数为：
          <span class="number">
           3744
          </span>
         </li>
         <li>
          词长
          <span class="number">
           7
          </span>
          的词数为：
          <span class="number">
           2206
          </span>
         </li>
         <li>
          词长
          <span class="number">
           8
          </span>
          的词数为：
          <span class="number">
           1321
          </span>
         </li>
         <li>
          词长
          <span class="number">
           9
          </span>
          的词数为：
          <span class="number">
           797
          </span>
         </li>
         <li>
          词长
          <span class="number">
           10
          </span>
          的词数为：
          <span class="number">
           632
          </span>
         </li>
         <li>
          词长
          <span class="number">
           11
          </span>
          的词数为：
          <span class="number">
           312
          </span>
         </li>
         <li>
          词长
          <span class="number">
           12
          </span>
          的词数为：
          <span class="number">
           282
          </span>
         </li>
         <li>
          词长
          <span class="number">
           13
          </span>
          的词数为：
          <span class="number">
           124
          </span>
         </li>
         <li>
          词长
          <span class="number">
           14
          </span>
          的词数为：
          <span class="number">
           116
          </span>
         </li>
         <li>
          词长
          <span class="number">
           15
          </span>
          的词数为：
          <span class="number">
           51
          </span>
         </li>
         <li>
          词长
          <span class="number">
           16
          </span>
          的词数为：
          <span class="number">
           25
          </span>
         </li>
         <li>
          词典平均词长：
          <span class="number">
           2.94809
          </span>
         </li>
         <li>
          字符数目：
          <span class="number">
           24960301
          </span>
         </li>
         <li>
          分词耗时：
          <span class="number">
           64014
          </span>
          毫秒
         </li>
         <li>
          分词速度：
          <span class="number">
           389.0
          </span>
          字符/毫秒
         </li>
         <li>
          执行之前剩余内存:
          <span class="number">
           2423.3901
          </span>
          –
          <span class="number">
           61.14509
          </span>
          +
          <span class="number">
           60.505272
          </span>
          =
          <span class="number">
           2422.7505
          </span>
         </li>
         <li>
          执行之后剩余内存:
          <span class="number">
           2423.3901
          </span>
          –
          <span class="number">
           961.08545
          </span>
          +
          <span class="number">
           203.32925
          </span>
          =
          <span class="number">
           1665.6339
          </span>
         </li>
         <li>
          cost time:
          <span class="number">
           64029
          </span>
          ms
         </li>
        </ol>
       </div>
       <p>
       </p>
       <div class="dp-highlighter" id="">
        <div class="bar">
         <div class="tools">
          Java代码
         </div>
        </div>
        <ol class="dp-j" start="1">
         <li>
          开始初始化词典
         </li>
         <li>
          dic.
          <span class="keyword">
           class
          </span>
          =org.apdplat.word.dictionary.impl.HashSet
         </li>
         <li>
          dic.path=dic.txt
         </li>
         <li>
          完成初始化词典，耗时
          <span class="number">
           293
          </span>
          毫秒，词数目：
          <span class="number">
           427452
          </span>
         </li>
         <li>
          词典最大词长：
          <span class="number">
           16
          </span>
         </li>
         <li>
          词长
          <span class="number">
           0
          </span>
          的词数为：
          <span class="number">
           1
          </span>
         </li>
         <li>
          词长
          <span class="number">
           1
          </span>
          的词数为：
          <span class="number">
           11581
          </span>
         </li>
         <li>
          词长
          <span class="number">
           2
          </span>
          的词数为：
          <span class="number">
           146497
          </span>
         </li>
         <li>
          词长
          <span class="number">
           3
          </span>
          的词数为：
          <span class="number">
           162776
          </span>
         </li>
         <li>
          词长
          <span class="number">
           4
          </span>
          的词数为：
          <span class="number">
           90855
          </span>
         </li>
         <li>
          词长
          <span class="number">
           5
          </span>
          的词数为：
          <span class="number">
           6132
          </span>
         </li>
         <li>
          词长
          <span class="number">
           6
          </span>
          的词数为：
          <span class="number">
           3744
          </span>
         </li>
         <li>
          词长
          <span class="number">
           7
          </span>
          的词数为：
          <span class="number">
           2206
          </span>
         </li>
         <li>
          词长
          <span class="number">
           8
          </span>
          的词数为：
          <span class="number">
           1321
          </span>
         </li>
         <li>
          词长
          <span class="number">
           9
          </span>
          的词数为：
          <span class="number">
           797
          </span>
         </li>
         <li>
          词长
          <span class="number">
           10
          </span>
          的词数为：
          <span class="number">
           632
          </span>
         </li>
         <li>
          词长
          <span class="number">
           11
          </span>
          的词数为：
          <span class="number">
           312
          </span>
         </li>
         <li>
          词长
          <span class="number">
           12
          </span>
          的词数为：
          <span class="number">
           282
          </span>
         </li>
         <li>
          词长
          <span class="number">
           13
          </span>
          的词数为：
          <span class="number">
           124
          </span>
         </li>
         <li>
          词长
          <span class="number">
           14
          </span>
          的词数为：
          <span class="number">
           116
          </span>
         </li>
         <li>
          词长
          <span class="number">
           15
          </span>
          的词数为：
          <span class="number">
           51
          </span>
         </li>
         <li>
          词长
          <span class="number">
           16
          </span>
          的词数为：
          <span class="number">
           25
          </span>
         </li>
         <li>
          词典平均词长：
          <span class="number">
           2.94809
          </span>
         </li>
         <li>
          字符数目：
          <span class="number">
           24960301
          </span>
         </li>
         <li>
          分词耗时：
          <span class="number">
           77254
          </span>
          毫秒
         </li>
         <li>
          分词速度：
          <span class="number">
           323.0
          </span>
          字符/毫秒
         </li>
         <li>
          执行之前剩余内存:
          <span class="number">
           2423.3901
          </span>
          –
          <span class="number">
           61.14509
          </span>
          +
          <span class="number">
           60.505295
          </span>
          =
          <span class="number">
           2422.7505
          </span>
         </li>
         <li>
          执行之后剩余内存:
          <span class="number">
           2423.3901
          </span>
          –
          <span class="number">
           900.46466
          </span>
          +
          <span class="number">
           726.91455
          </span>
          =
          <span class="number">
           2249.84
          </span>
         </li>
         <li>
          cost time:
          <span class="number">
           77271
          </span>
          ms
         </li>
        </ol>
       </div>
       <p>
       </p>
       <p>
        在上篇文章
        <a href="http://yangshangchuan.iteye.com/blog/2031813" target="_blank" title="http://yangshangchuan.iteye.com/blog/2031813">
         基于词典的正向最大匹配算法
        </a>
        中，我们已经优化了词典查找算法（DIC.contains(tryWord)）的性能（百万次查询只要一秒左右的时间），即使经过优化后TrieV3仍然比HashSet慢4倍，也不影响它在分词算法中的作用，从上面的数据可以看到，TrieV3的整体分词性能领先HashSet十五个百分点（15%），而且内存占用只有HashSet的80%。
       </p>
       <p>
       </p>
       <p>
        如何来优化分词算法呢？分词算法有什么问题吗？
       </p>
       <p>
       </p>
       <p>
        回顾一下代码：
       </p>
       <p>
       </p>
       <div class="dp-highlighter" id="">
        <div class="bar">
         <div class="tools">
          Java代码
         </div>
        </div>
        <ol class="dp-j" start="1">
         <li>
          <span class="keyword">
           public
          </span>
          <span class="keyword">
           static
          </span>
          List&lt;String&gt; seg(String text){
         </li>
         <li>
          List&lt;String&gt; result =
          <span class="keyword">
           new
          </span>
          ArrayList&lt;&gt;();
         </li>
         <li>
          <span class="keyword">
           while
          </span>
          (text.length()&gt;
          <span class="number">
           0
          </span>
          ){
         </li>
         <li>
          <span class="keyword">
           int
          </span>
          len=MAX_LENGTH;
         </li>
         <li>
          <span class="keyword">
           if
          </span>
          (text.length()&lt;len){
         </li>
         <li>
          len=text.length();
         </li>
         <li>
          }
         </li>
         <li>
          <span class="comment">
           //取指定的最大长度的文本去词典里面匹配
          </span>
         </li>
         <li>
          String tryWord = text.substring(
          <span class="number">
           0
          </span>
          ,
          <span class="number">
           0
          </span>
          +len);
         </li>
         <li>
          <span class="keyword">
           while
          </span>
          (!DIC.contains(tryWord)){
         </li>
         <li>
          <span class="comment">
           //如果长度为一且在词典中未找到匹配，则按长度为一切分
          </span>
         </li>
         <li>
          <span class="keyword">
           if
          </span>
          (tryWord.length()==
          <span class="number">
           1
          </span>
          ){
         </li>
         <li>
          <span class="keyword">
           break
          </span>
          ;
         </li>
         <li>
          }
         </li>
         <li>
          <span class="comment">
           //如果匹配不到，则长度减一继续匹配
          </span>
         </li>
         <li>
          tryWord=tryWord.substring(
          <span class="number">
           0
          </span>
          , tryWord.length()-
          <span class="number">
           1
          </span>
          );
         </li>
         <li>
          }
         </li>
         <li>
          result.add(tryWord);
         </li>
         <li>
          <span class="comment">
           //从待分词文本中去除已经分词的文本
          </span>
         </li>
         <li>
          text=text.substring(tryWord.length());
         </li>
         <li>
          }
         </li>
         <li>
          <span class="keyword">
           return
          </span>
          result;
         </li>
         <li>
          }
         </li>
        </ol>
       </div>
       <p>
       </p>
       <p>
        分析一下算法复杂性，最坏情况为切分出来的每个词的长度都为一（即DIC.contains(tryWord)始终为false），因此算法的复杂度约为外层循环数*内层循环数（即 文本长度*最大词长）=25025017*16=400400272，以TrieV3的查找性能来说，4亿次查询花费的时间大约8分钟左右。
       </p>
       <p>
       </p>
       <p>
        进一步查看算法，发现外层循环有2个substring方法调用，内层循环有1个substring方法调用，substring方法内部new了一个String对象，构造String对象的时候又调用了System.arraycopy来拷贝数组。
       </p>
       <p>
       </p>
       <p>
        最坏情况下，25025017*2+25025017*16=50050034+400400272=450450306，需要构造4.5亿个String对象和拷贝4.5亿次数组。
       </p>
       <p>
       </p>
       <p>
        怎么来优化呢？
       </p>
       <p>
       </p>
       <p>
        除了我们不得不把切分出来的词加入result中外，其他的两个substring是可以去掉的。这样，最坏情况下我们需要构造的String对象个数和拷贝数组的次数就
        <strong>
         从4.5亿次降低为25025017次，只有原来的5.6%
        </strong>
        。
       </p>
       <p>
       </p>
       <p>
        看看改进后的代码：
       </p>
       <p>
       </p>
       <div class="dp-highlighter" id="">
        <div class="bar">
         <div class="tools">
          Java代码
         </div>
        </div>
        <ol class="dp-j" start="1">
         <li>
          <span class="keyword">
           public
          </span>
          <span class="keyword">
           static
          </span>
          List&lt;String&gt; seg(String text){
         </li>
         <li>
          List&lt;String&gt; result =
          <span class="keyword">
           new
          </span>
          ArrayList&lt;&gt;();
         </li>
         <li>
          <span class="comment">
           //文本长度
          </span>
         </li>
         <li>
          <span class="keyword">
           final
          </span>
          <span class="keyword">
           int
          </span>
          textLen=text.length();
         </li>
         <li>
          <span class="comment">
           //从未分词的文本中截取的长度
          </span>
         </li>
         <li>
          <span class="keyword">
           int
          </span>
          len=DIC.getMaxLength();
         </li>
         <li>
          <span class="comment">
           //剩下未分词的文本的索引
          </span>
         </li>
         <li>
          <span class="keyword">
           int
          </span>
          start=
          <span class="number">
           0
          </span>
          ;
         </li>
         <li>
          <span class="comment">
           //只要有词未切分完就一直继续
          </span>
         </li>
         <li>
          <span class="keyword">
           while
          </span>
          (start&lt;textLen){
         </li>
         <li>
          <span class="keyword">
           if
          </span>
          (len&gt;textLen-start){
         </li>
         <li>
          <span class="comment">
           //如果未分词的文本的长度小于截取的长度
          </span>
         </li>
         <li>
          <span class="comment">
           //则缩短截取的长度
          </span>
         </li>
         <li>
          len=textLen-start;
         </li>
         <li>
          }
         </li>
         <li>
          <span class="comment">
           //用长为len的字符串查词典
          </span>
         </li>
         <li>
          <span class="keyword">
           while
          </span>
          (!DIC.contains(text, start, len)){
         </li>
         <li>
          <span class="comment">
           //如果长度为一且在词典中未找到匹配
          </span>
         </li>
         <li>
          <span class="comment">
           //则按长度为一切分
          </span>
         </li>
         <li>
          <span class="keyword">
           if
          </span>
          (len==
          <span class="number">
           1
          </span>
          ){
         </li>
         <li>
          <span class="keyword">
           break
          </span>
          ;
         </li>
         <li>
          }
         </li>
         <li>
          <span class="comment">
           //如果查不到，则长度减一后继续
          </span>
         </li>
         <li>
          len–;
         </li>
         <li>
          }
         </li>
         <li>
          result.add(text.substring(start, start+len));
         </li>
         <li>
          <span class="comment">
           //从待分词文本中向后移动索引，滑过已经分词的文本
          </span>
         </li>
         <li>
          start+=len;
         </li>
         <li>
          <span class="comment">
           //每一次成功切词后都要重置截取长度
          </span>
         </li>
         <li>
          len=DIC.getMaxLength();
         </li>
         <li>
          }
         </li>
         <li>
          <span class="keyword">
           return
          </span>
          result;
         </li>
         <li>
          }
         </li>
         <li>
          <span class="keyword">
           public
          </span>
          <span class="keyword">
           static
          </span>
          List&lt;String&gt; segReverse(String text){
         </li>
         <li>
          Stack&lt;String&gt; result =
          <span class="keyword">
           new
          </span>
          Stack&lt;&gt;();
         </li>
         <li>
          <span class="comment">
           //文本长度
          </span>
         </li>
         <li>
          <span class="keyword">
           final
          </span>
          <span class="keyword">
           int
          </span>
          textLen=text.length();
         </li>
         <li>
          <span class="comment">
           //从未分词的文本中截取的长度
          </span>
         </li>
         <li>
          <span class="keyword">
           int
          </span>
          len=DIC.getMaxLength();
         </li>
         <li>
          <span class="comment">
           //剩下未分词的文本的索引
          </span>
         </li>
         <li>
          <span class="keyword">
           int
          </span>
          start=textLen-len;
         </li>
         <li>
          <span class="comment">
           //处理文本长度小于最大词长的情况
          </span>
         </li>
         <li>
          <span class="keyword">
           if
          </span>
          (start&lt;
          <span class="number">
           0
          </span>
          ){
         </li>
         <li>
          start=
          <span class="number">
           0
          </span>
          ;
         </li>
         <li>
          }
         </li>
         <li>
          <span class="keyword">
           if
          </span>
          (len&gt;textLen-start){
         </li>
         <li>
          <span class="comment">
           //如果未分词的文本的长度小于截取的长度
          </span>
         </li>
         <li>
          <span class="comment">
           //则缩短截取的长度
          </span>
         </li>
         <li>
          len=textLen-start;
         </li>
         <li>
          }
         </li>
         <li>
          <span class="comment">
           //只要有词未切分完就一直继续
          </span>
         </li>
         <li>
          <span class="keyword">
           while
          </span>
          (start&gt;=
          <span class="number">
           0
          </span>
          &amp;&amp; len&gt;
          <span class="number">
           0
          </span>
          ){
         </li>
         <li>
          <span class="comment">
           //用长为len的字符串查词典
          </span>
         </li>
         <li>
          <span class="keyword">
           while
          </span>
          (!DIC.contains(text, start, len)){
         </li>
         <li>
          <span class="comment">
           //如果长度为一且在词典中未找到匹配
          </span>
         </li>
         <li>
          <span class="comment">
           //则按长度为一切分
          </span>
         </li>
         <li>
          <span class="keyword">
           if
          </span>
          (len==
          <span class="number">
           1
          </span>
          ){
         </li>
         <li>
          <span class="keyword">
           break
          </span>
          ;
         </li>
         <li>
          }
         </li>
         <li>
          <span class="comment">
           //如果查不到，则长度减一
          </span>
         </li>
         <li>
          <span class="comment">
           //索引向后移动一个字，然后继续
          </span>
         </li>
         <li>
          len–;
         </li>
         <li>
          start++;
         </li>
         <li>
          }
         </li>
         <li>
          result.push(text.substring(start, start+len));
         </li>
         <li>
          <span class="comment">
           //每一次成功切词后都要重置截取长度
          </span>
         </li>
         <li>
          len=DIC.getMaxLength();
         </li>
         <li>
          <span class="keyword">
           if
          </span>
          (len&gt;start){
         </li>
         <li>
          <span class="comment">
           //如果未分词的文本的长度小于截取的长度
          </span>
         </li>
         <li>
          <span class="comment">
           //则缩短截取的长度
          </span>
         </li>
         <li>
          len=start;
         </li>
         <li>
          }
         </li>
         <li>
          <span class="comment">
           //每一次成功切词后都要重置开始索引位置
          </span>
         </li>
         <li>
          <span class="comment">
           //从待分词文本中向前移动最大词长个索引
          </span>
         </li>
         <li>
          <span class="comment">
           //将未分词的文本纳入下次分词的范围
          </span>
         </li>
         <li>
          start-=len;
         </li>
         <li>
          }
         </li>
         <li>
          len=result.size();
         </li>
         <li>
          List&lt;String&gt; list =
          <span class="keyword">
           new
          </span>
          ArrayList&lt;&gt;(len);
         </li>
         <li>
          <span class="keyword">
           for
          </span>
          (
          <span class="keyword">
           int
          </span>
          i=
          <span class="number">
           0
          </span>
          ;i&lt;len;i++){
         </li>
         <li>
          list.add(result.pop());
         </li>
         <li>
          }
         </li>
         <li>
          <span class="keyword">
           return
          </span>
          list;
         </li>
         <li>
          }
         </li>
        </ol>
       </div>
       <p>
       </p>
       <p>
        对于正向最大匹配算法，代码行数从23增加为33，对于逆向最大匹配算法，代码行数从28增加为51，除了代码行数的增加，代码更复杂，可读性和可维护性也更差，这就是性能的代价！所以，不要过早优化，不要做不成熟的优化，因为不是所有的场合都需要高性能，在数据规模未达到一定程度的时候，各种算法和数据结构的差异表现不大，至少那个差异对你无任何影响。你可能会说，要考虑到明天，要考虑将来，你有你自己的道理，不过，我还是坚持不过度设计，不过早设计，通过单元测试和持续重构来应对变化，不为遥不可及的将来浪费今天，下一秒会发生什么谁知道呢？更不用说明天！因为有单元测试这张安全防护网，所以在出现性能问题的时候，我们可以放心、大胆、迅速地重构来优化性能。
       </p>
       <p>
       </p>
       <p>
        下面看看改进之后的性能（对比TrieV3和HashSet的表现）：
       </p>
       <p>
       </p>
       <div class="dp-highlighter" id="">
        <div class="bar">
         <div class="tools">
          Java代码
         </div>
        </div>
        <ol class="dp-j" start="1">
         <li>
          开始初始化词典
         </li>
         <li>
          dic.
          <span class="keyword">
           class
          </span>
          =org.apdplat.word.dictionary.impl.TrieV3
         </li>
         <li>
          dic.path=dic.txt
         </li>
         <li>
          完成初始化词典，耗时
          <span class="number">
           689
          </span>
          毫秒，词数目：
          <span class="number">
           427452
          </span>
         </li>
         <li>
          词典最大词长：
          <span class="number">
           16
          </span>
         </li>
         <li>
          词长
          <span class="number">
           0
          </span>
          的词数为：
          <span class="number">
           1
          </span>
         </li>
         <li>
          词长
          <span class="number">
           1
          </span>
          的词数为：
          <span class="number">
           11581
          </span>
         </li>
         <li>
          词长
          <span class="number">
           2
          </span>
          的词数为：
          <span class="number">
           146497
          </span>
         </li>
         <li>
          词长
          <span class="number">
           3
          </span>
          的词数为：
          <span class="number">
           162776
          </span>
         </li>
         <li>
          词长
          <span class="number">
           4
          </span>
          的词数为：
          <span class="number">
           90855
          </span>
         </li>
         <li>
          词长
          <span class="number">
           5
          </span>
          的词数为：
          <span class="number">
           6132
          </span>
         </li>
         <li>
          词长
          <span class="number">
           6
          </span>
          的词数为：
          <span class="number">
           3744
          </span>
         </li>
         <li>
          词长
          <span class="number">
           7
          </span>
          的词数为：
          <span class="number">
           2206
          </span>
         </li>
         <li>
          词长
          <span class="number">
           8
          </span>
          的词数为：
          <span class="number">
           1321
          </span>
         </li>
         <li>
          词长
          <span class="number">
           9
          </span>
          的词数为：
          <span class="number">
           797
          </span>
         </li>
         <li>
          词长
          <span class="number">
           10
          </span>
          的词数为：
          <span class="number">
           632
          </span>
         </li>
         <li>
          词长
          <span class="number">
           11
          </span>
          的词数为：
          <span class="number">
           312
          </span>
         </li>
         <li>
          词长
          <span class="number">
           12
          </span>
          的词数为：
          <span class="number">
           282
          </span>
         </li>
         <li>
          词长
          <span class="number">
           13
          </span>
          的词数为：
          <span class="number">
           124
          </span>
         </li>
         <li>
          词长
          <span class="number">
           14
          </span>
          的词数为：
          <span class="number">
           116
          </span>
         </li>
         <li>
          词长
          <span class="number">
           15
          </span>
          的词数为：
          <span class="number">
           51
          </span>
         </li>
         <li>
          词长
          <span class="number">
           16
          </span>
          的词数为：
          <span class="number">
           25
          </span>
         </li>
         <li>
          词典平均词长：
          <span class="number">
           2.94809
          </span>
         </li>
         <li>
          字符数目：
          <span class="number">
           24960301
          </span>
         </li>
         <li>
          分词耗时：
          <span class="number">
           24782
          </span>
          毫秒
         </li>
         <li>
          分词速度：
          <span class="number">
           1007.0
          </span>
          字符/毫秒
         </li>
         <li>
          执行之前剩余内存:
          <span class="number">
           2423.3901
          </span>
          –
          <span class="number">
           61.14509
          </span>
          +
          <span class="number">
           60.505272
          </span>
          =
          <span class="number">
           2422.7505
          </span>
         </li>
         <li>
          执行之后剩余内存:
          <span class="number">
           2423.3901
          </span>
          –
          <span class="number">
           732.0371
          </span>
          +
          <span class="number">
           308.87476
          </span>
          =
          <span class="number">
           2000.2278
          </span>
         </li>
         <li>
          cost time:
          <span class="number">
           25007
          </span>
          ms
         </li>
        </ol>
       </div>
       <p>
       </p>
       <div class="dp-highlighter" id="">
        <div class="bar">
         <div class="tools">
          Java代码
         </div>
        </div>
        <ol class="dp-j" start="1">
         <li>
          开始初始化词典
         </li>
         <li>
          dic.
          <span class="keyword">
           class
          </span>
          =org.apdplat.word.dictionary.impl.HashSet
         </li>
         <li>
          dic.path=dic.txt
         </li>
         <li>
          完成初始化词典，耗时
          <span class="number">
           293
          </span>
          毫秒，词数目：
          <span class="number">
           427452
          </span>
         </li>
         <li>
          词典最大词长：
          <span class="number">
           16
          </span>
         </li>
         <li>
          词长
          <span class="number">
           0
          </span>
          的词数为：
          <span class="number">
           1
          </span>
         </li>
         <li>
          词长
          <span class="number">
           1
          </span>
          的词数为：
          <span class="number">
           11581
          </span>
         </li>
         <li>
          词长
          <span class="number">
           2
          </span>
          的词数为：
          <span class="number">
           146497
          </span>
         </li>
         <li>
          词长
          <span class="number">
           3
          </span>
          的词数为：
          <span class="number">
           162776
          </span>
         </li>
         <li>
          词长
          <span class="number">
           4
          </span>
          的词数为：
          <span class="number">
           90855
          </span>
         </li>
         <li>
          词长
          <span class="number">
           5
          </span>
          的词数为：
          <span class="number">
           6132
          </span>
         </li>
         <li>
          词长
          <span class="number">
           6
          </span>
          的词数为：
          <span class="number">
           3744
          </span>
         </li>
         <li>
          词长
          <span class="number">
           7
          </span>
          的词数为：
          <span class="number">
           2206
          </span>
         </li>
         <li>
          词长
          <span class="number">
           8
          </span>
          的词数为：
          <span class="number">
           1321
          </span>
         </li>
         <li>
          词长
          <span class="number">
           9
          </span>
          的词数为：
          <span class="number">
           797
          </span>
         </li>
         <li>
          词长
          <span class="number">
           10
          </span>
          的词数为：
          <span class="number">
           632
          </span>
         </li>
         <li>
          词长
          <span class="number">
           11
          </span>
          的词数为：
          <span class="number">
           312
          </span>
         </li>
         <li>
          词长
          <span class="number">
           12
          </span>
          的词数为：
          <span class="number">
           282
          </span>
         </li>
         <li>
          词长
          <span class="number">
           13
          </span>
          的词数为：
          <span class="number">
           124
          </span>
         </li>
         <li>
          词长
          <span class="number">
           14
          </span>
          的词数为：
          <span class="number">
           116
          </span>
         </li>
         <li>
          词长
          <span class="number">
           15
          </span>
          的词数为：
          <span class="number">
           51
          </span>
         </li>
         <li>
          词长
          <span class="number">
           16
          </span>
          的词数为：
          <span class="number">
           25
          </span>
         </li>
         <li>
          词典平均词长：
          <span class="number">
           2.94809
          </span>
         </li>
         <li>
          字符数目：
          <span class="number">
           24960301
          </span>
         </li>
         <li>
          分词耗时：
          <span class="number">
           40913
          </span>
          毫秒
         </li>
         <li>
          分词速度：
          <span class="number">
           610.0
          </span>
          字符/毫秒
         </li>
         <li>
          执行之前剩余内存:
          <span class="number">
           907.8702
          </span>
          –
          <span class="number">
           61.14509
          </span>
          +
          <span class="number">
           60.505295
          </span>
          =
          <span class="number">
           907.2304
          </span>
         </li>
         <li>
          执行之后剩余内存:
          <span class="number">
           907.8702
          </span>
          –
          <span class="number">
           165.4784
          </span>
          +
          <span class="number">
           123.30369
          </span>
          =
          <span class="number">
           865.6955
          </span>
         </li>
         <li>
          cost time:
          <span class="number">
           40928
          </span>
          ms
         </li>
        </ol>
       </div>
       <p>
       </p>
       <p>
        可以看到分词算法优化的效果很明显，对于TrieV3来说，提升了2.5倍，对于HashSet来说，提升了1.9倍。我们看看HashSet的实现：
       </p>
       <p>
       </p>
       <div class="dp-highlighter" id="">
        <div class="bar">
         <div class="tools">
          Java代码
         </div>
        </div>
        <ol class="dp-j" start="1">
         <li>
          <span class="keyword">
           public
          </span>
          <span class="keyword">
           class
          </span>
          HashSet
          <span class="keyword">
           implements
          </span>
          Dictionary{
         </li>
         <li>
          <span class="keyword">
           private
          </span>
          Set&lt;String&gt; set =
          <span class="keyword">
           new
          </span>
          java.util.HashSet&lt;&gt;();
         </li>
         <li>
          <span class="keyword">
           private
          </span>
          <span class="keyword">
           int
          </span>
          maxLength;
         </li>
         <li>
          <span class="annotation">
           @Override
          </span>
         </li>
         <li>
          <span class="keyword">
           public
          </span>
          <span class="keyword">
           int
          </span>
          getMaxLength() {
         </li>
         <li>
          <span class="keyword">
           return
          </span>
          maxLength;
         </li>
         <li>
          }
         </li>
         <li>
          <span class="annotation">
           @Override
          </span>
         </li>
         <li>
          <span class="keyword">
           public
          </span>
          <span class="keyword">
           boolean
          </span>
          contains(String item,
          <span class="keyword">
           int
          </span>
          start,
          <span class="keyword">
           int
          </span>
          length) {
         </li>
         <li>
          <span class="keyword">
           return
          </span>
          set.contains(item.substring(start, start+length));
         </li>
         <li>
          }
         </li>
         <li>
          <span class="annotation">
           @Override
          </span>
         </li>
         <li>
          <span class="keyword">
           public
          </span>
          <span class="keyword">
           boolean
          </span>
          contains(String item) {
         </li>
         <li>
          <span class="keyword">
           return
          </span>
          set.contains(item);
         </li>
         <li>
          }
         </li>
         <li>
          <span class="annotation">
           @Override
          </span>
         </li>
         <li>
          <span class="keyword">
           public
          </span>
          <span class="keyword">
           void
          </span>
          addAll(List&lt;String&gt; items) {
         </li>
         <li>
          <span class="keyword">
           for
          </span>
          (String item : items){
         </li>
         <li>
          add(item);
         </li>
         <li>
          }
         </li>
         <li>
          }
         </li>
         <li>
          <span class="annotation">
           @Override
          </span>
         </li>
         <li>
          <span class="keyword">
           public
          </span>
          <span class="keyword">
           void
          </span>
          add(String item) {
         </li>
         <li>
          <span class="comment">
           //去掉首尾空白字符
          </span>
         </li>
         <li>
          item=item.trim();
         </li>
         <li>
          <span class="keyword">
           int
          </span>
          len = item.length();
         </li>
         <li>
          <span class="keyword">
           if
          </span>
          (len &lt;
          <span class="number">
           1
          </span>
          ){
         </li>
         <li>
          <span class="comment">
           //长度小于1则忽略
          </span>
         </li>
         <li>
          <span class="keyword">
           return
          </span>
          ;
         </li>
         <li>
          }
         </li>
         <li>
          <span class="keyword">
           if
          </span>
          (len&gt;maxLength){
         </li>
         <li>
          maxLength=len;
         </li>
         <li>
          }
         </li>
         <li>
          set.add(item);
         </li>
         <li>
          }
         </li>
         <li>
          }
         </li>
        </ol>
       </div>
       <p>
       </p>
       <p>
        JDK的HashSet没有这里优化所使用的contains(String item, int start, int length)方法，所以用了substring，这是HashSet提速没有TrieV3大的原因之一。
       </p>
       <p>
       </p>
       <p>
        看一下改进的算法和原来的算法的对比：
       </p>
       <p>
       </p>
       <p>
        正向最大匹配算法：
        <br/>
        <img src="http://dataunion.org/wp-content/uploads/2015/05/49f5cf76-e3fd-332a-9391-4ed5dae6c822.png"/>
        <br/>
        逆向最大匹配算法：
        <br/>
        <img src="http://dataunion.org/wp-content/uploads/2015/05/87ac24a3-3d38-3583-9096-33a7e71f45c1.png"/>
        <br/>
       </p>
       <p>
       </p>
       <p>
        <a href="https://github.com/ysc/word" target="_blank" title="https://github.com/ysc/word">
         代码托管于GITHUB
        </a>
       </p>
       <p>
       </p>
       <p>
        参考资料：
       </p>
       <p>
        1、
        <a href="http://pan.baidu.com/s/1qWwdhTE" target="_blank" title="http://pan.baidu.com/s/1qWwdhTE">
         中文分词十年回顾
        </a>
       </p>
       <p>
        2、
        <a href="http://pan.baidu.com/s/1i3n3Twp" target="_blank" title="http://pan.baidu.com/s/1i3n3Twp">
         中文信息处理中的分词问题
        </a>
       </p>
       <p>
        3、
        <a href="http://pan.baidu.com/s/1hqqTLfm" target="_blank" title="http://pan.baidu.com/s/1hqqTLfm">
         汉语自动分词词典机制的实验研究
        </a>
       </p>
       <p>
        4、
        <a href="http://pan.baidu.com/s/1gdeK6NT" target="_blank" title="http://pan.baidu.com/s/1gdeK6NT">
         由字构词_中文分词新方法
        </a>
       </p>
       <p>
        5、
        <a href="http://pan.baidu.com/s/1dD5TaVJ" target="_blank" title="http://pan.baidu.com/s/1dD5TaVJ">
         汉语自动分词研究评述
        </a>
       </p>
       <p>
       </p>
       <blockquote>
        <p>
         作者：杨尚川
        </p>
        <p>
         文章出处：http://yangshangchuan.iteye.com/blog/2033843
        </p>
       </blockquote>
      </div>
      <div>
       <strong>
        注：转载文章均来自于公开网络，仅供学习使用，不会用于任何商业用途，如果侵犯到原作者的权益，请您与我们联系删除或者授权事宜，联系邮箱：contact@dataunion.org。转载数盟网站文章请注明原文章作者，否则产生的任何版权纠纷与数盟无关。
       </strong>
      </div>
      <!--content_text-->
      <div class="fenxian">
       <!-- JiaThis Button BEGIN -->
       <div class="jiathis_style_32x32">
        <p class="jiathis_button_weixin">
        </p>
        <p class="jiathis_button_tsina">
        </p>
        <p class="jiathis_button_qzone">
        </p>
        <p class="jiathis_button_cqq">
        </p>
        <p class="jiathis_button_tumblr">
        </p>
        <a class="jiathis jiathis_txt jtico jtico_jiathis" href="http://www.jiathis.com/share" target="_blank">
        </a>
        <p class="jiathis_counter_style">
        </p>
       </div>
       <!-- JiaThis Button END -->
      </div>
     </article>
     <!--content-->
     <!--相关文章-->
     <div class="xianguan">
      <div class="xianguantitle">
       相关文章！
      </div>
      <ul class="pic">
       <li>
        <a href="http://dataunion.org/24220.html">
         <img src="http://dataunion.org/wp-content/uploads/2016/05/100910rrxp5plglxk4lcle-291x200.png"/>
        </a>
        <a class="link" href="http://dataunion.org/24220.html" rel="bookmark" title="520大数据：八成男性期待被表白 “套路”也是爱">
         520大数据：八成男性期待被表白 “套路”也是爱
        </a>
       </li>
       <li>
        <a href="http://dataunion.org/23785.html">
         <img src="http://dataunion.org/wp-content/uploads/2016/04/u7145986293872240263fm21gp0-298x200.jpg"/>
        </a>
        <a class="link" href="http://dataunion.org/23785.html" rel="bookmark" title="Docker安全基准：22项新增要点概述">
         Docker安全基准：22项新增要点概述
        </a>
       </li>
       <li>
        <a href="http://dataunion.org/23703.html">
         <img src="http://dataunion.org/wp-content/uploads/2016/04/1317020-300x163.jpg"/>
        </a>
        <a class="link" href="http://dataunion.org/23703.html" rel="bookmark" title="推荐：五个不容错过的数据科学家博客">
         推荐：五个不容错过的数据科学家博客
        </a>
       </li>
       <li>
        <a href="http://dataunion.org/23507.html">
         <img src="http://dataunion.org/wp-content/uploads/2016/03/110606wjpugdldig4idddn.jpg"/>
        </a>
        <a class="link" href="http://dataunion.org/23507.html" rel="bookmark" title="解密深度学习在智能推荐系统的实践与应用">
         解密深度学习在智能推荐系统的实践与应用
        </a>
       </li>
      </ul>
     </div>
     <!--相关文章-->
     <div class="comment" id="comments">
      <!-- You can start editing here. -->
      <!-- If comments are open, but there are no comments. -->
      <div class="title">
       期待你一针见血的评论，Come on！
      </div>
      <div id="respond">
       <p>
        不用想啦，马上
        <a href="http://dataunion.org/wp-login.php?redirect_to=http%3A%2F%2Fdataunion.org%2F16736.html">
         "登录"
        </a>
        发表自已的想法.
       </p>
      </div>
     </div>
     <!-- .nav-single -->
    </div>
    <!--Container End-->
    <aside id="sitebar">
     <div class="sitebar_list2">
      <div class="wptag">
       <span class="tagtitle">
        热门标签+
       </span>
       <div class="tagg">
        <ul class="menu" id="menu-%e5%8f%8b%e6%83%85%e9%93%be%e6%8e%a5">
         <li class="menu-item menu-item-type-custom menu-item-object-custom menu-item-1605" id="menu-item-1605">
          <a href="http://taidizh.com/">
           泰迪智慧
          </a>
         </li>
         <li class="menu-item menu-item-type-custom menu-item-object-custom menu-item-20884" id="menu-item-20884">
          <a href="http://www.transwarp.cn/">
           星环科技
          </a>
         </li>
         <li class="menu-item menu-item-type-custom menu-item-object-custom menu-item-3538" id="menu-item-3538">
          <a href="http://datall.org/">
           珈和遥感
          </a>
         </li>
         <li class="menu-item menu-item-type-custom menu-item-object-custom menu-item-20888" id="menu-item-20888">
          <a href="http://www.chinahadoop.cn/">
           小象学院
          </a>
         </li>
        </ul>
       </div>
      </div>
     </div>
     <div class="sitebar_list">
      <div class="textwidget">
       <div align="center">
        <a href="http://study.163.com/course/courseMain.htm?courseId=991022" target="_blank">
         <img src="http://dataunion.org/wp-content/uploads/2016/03/dv.jpg"/>
        </a>
       </div>
      </div>
     </div>
     <div class="sitebar_list">
      <h4 class="sitebar_title">
       文章分类
      </h4>
      <div class="tagcloud">
       <a class="tag-link-44" href="http://dataunion.org/category/industry/demo" style="font-size: 10.204724409449pt;" title="4个话题">
        Demo展示
       </a>
       <a class="tag-link-31" href="http://dataunion.org/category/experts" style="font-size: 15.826771653543pt;" title="52个话题">
        专家团队
       </a>
       <a class="tag-link-870" href="http://dataunion.org/category/tech/ai" style="font-size: 19.795275590551pt;" title="273个话题">
        人工智能
       </a>
       <a class="tag-link-488" href="http://dataunion.org/category/%e5%8a%a0%e5%85%a5%e6%95%b0%e7%9b%9f" style="font-size: 8pt;" title="1个话题">
        加入数盟
       </a>
       <a class="tag-link-869" href="http://dataunion.org/category/tech/viz" style="font-size: 17.204724409449pt;" title="93个话题">
        可视化
       </a>
       <a class="tag-link-30" href="http://dataunion.org/category/partners" style="font-size: 10.645669291339pt;" title="5个话题">
        合作伙伴
       </a>
       <a class="tag-link-889" href="http://dataunion.org/category/parterc" style="font-size: 11.582677165354pt;" title="8个话题">
        合作会议
       </a>
       <a class="tag-link-104" href="http://dataunion.org/category/books" style="font-size: 12.96062992126pt;" title="15个话题">
        图书
       </a>
       <a class="tag-link-220" href="http://dataunion.org/category/tech/base" style="font-size: 19.850393700787pt;" title="281个话题">
        基础架构
       </a>
       <a class="tag-link-219" href="http://dataunion.org/category/tech/analysis" style="font-size: 19.409448818898pt;" title="232个话题">
        数据分析
       </a>
       <a class="tag-link-887" href="http://dataunion.org/category/tech/dm" style="font-size: 13.291338582677pt;" title="17个话题">
        数据挖掘
       </a>
       <a class="tag-link-34" href="http://dataunion.org/category/tech" style="font-size: 20.732283464567pt;" title="404个话题">
        文章
       </a>
       <a class="tag-link-1" href="http://dataunion.org/category/uncategorized" style="font-size: 22pt;" title="693个话题">
        未分类
       </a>
       <a class="tag-link-4" href="http://dataunion.org/category/events" style="font-size: 14.503937007874pt;" title="29个话题">
        活动
       </a>
       <a class="tag-link-890" href="http://dataunion.org/category/tech/%e6%b7%b1%e5%ba%a6%e5%ad%a6%e4%b9%a0" style="font-size: 10.204724409449pt;" title="4个话题">
        深度学习
       </a>
       <a class="tag-link-221" href="http://dataunion.org/category/tech/devl" style="font-size: 18.968503937008pt;" title="193个话题">
        编程语言
       </a>
       <a class="tag-link-888" href="http://dataunion.org/category/career" style="font-size: 15.661417322835pt;" title="48个话题">
        职业规划
       </a>
       <a class="tag-link-5" href="http://dataunion.org/category/jobs" style="font-size: 14.11811023622pt;" title="25个话题">
        职位
       </a>
       <a class="tag-link-871" href="http://dataunion.org/category/industry" style="font-size: 15.716535433071pt;" title="49个话题">
        行业
       </a>
       <a class="tag-link-613" href="http://dataunion.org/category/industry/case" style="font-size: 16.984251968504pt;" title="84个话题">
        行业应用
       </a>
       <a class="tag-link-885" href="http://dataunion.org/category/industry/news" style="font-size: 17.425196850394pt;" title="102个话题">
        行业资讯
       </a>
       <a class="tag-link-10" href="http://dataunion.org/category/training" style="font-size: 14.228346456693pt;" title="26个话题">
        课程
       </a>
       <a class="tag-link-16" href="http://dataunion.org/category/sources" style="font-size: 15.661417322835pt;" title="48个话题">
        资源
       </a>
      </div>
     </div>
     <div class="sitebar_list">
      <h4 class="sitebar_title">
       功能
      </h4>
      <ul>
       <li>
        <a href="http://dataunion.org/wp-login.php?action=register">
         注册
        </a>
       </li>
       <li>
        <a href="http://dataunion.org/wp-login.php">
         登录
        </a>
       </li>
       <li>
        <a href="http://dataunion.org/feed">
         文章
         <abbr title="Really Simple Syndication">
          RSS
         </abbr>
        </a>
       </li>
       <li>
        <a href="http://dataunion.org/comments/feed">
         评论
         <abbr title="Really Simple Syndication">
          RSS
         </abbr>
        </a>
       </li>
       <li>
        <a href="https://cn.wordpress.org/" title="基于WordPress，一个优美、先进的个人信息发布平台。">
         WordPress.org
        </a>
       </li>
      </ul>
     </div>
    </aside>
    <div class="clear">
    </div>
   </div>
   <!--main-->
   ﻿
   <footer id="dibu">
    <div class="about">
     <div class="right">
      <ul class="menu" id="menu-%e5%ba%95%e9%83%a8%e8%8f%9c%e5%8d%95">
       <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-18024" id="menu-item-18024">
        <a href="http://dataunion.org/category/partners">
         合作伙伴
        </a>
       </li>
       <li class="menu-item menu-item-type-post_type menu-item-object-page menu-item-20881" id="menu-item-20881">
        <a href="http://dataunion.org/contribute">
         文章投稿
        </a>
       </li>
       <li class="menu-item menu-item-type-taxonomy menu-item-object-category menu-item-20872" id="menu-item-20872">
        <a href="http://dataunion.org/category/%e5%8a%a0%e5%85%a5%e6%95%b0%e7%9b%9f">
         加入数盟
        </a>
       </li>
       <li class="menu-item menu-item-type-post_type menu-item-object-page menu-item-22441" id="menu-item-22441">
        <a href="http://dataunion.org/f-links">
         友情链接
        </a>
       </li>
       <li class="menu-item menu-item-type-post_type menu-item-object-page menu-item-20874" id="menu-item-20874">
        <a href="http://dataunion.org/aboutus">
         关于数盟
        </a>
       </li>
      </ul>
      <p class="banquan">
       数盟社区        ，
        做最棒的数据科学社区
      </p>
     </div>
     <div class="left">
      <ul class="bottomlist">
       <li>
        <a href="http://weibo.com/DataScientistUnion  " target="_blank" 　title="">
         <img src="http://dataunion.org/wp-content/themes/yzipi/images/weibo.png"/>
        </a>
       </li>
       <li>
        <a class="cd-popup-trigger" href="http://dataunion.org/16736.html#0">
         <img src="http://dataunion.org/wp-content/themes/yzipi/images/weixin.png"/>
        </a>
       </li>
      </ul>
      <div class="cd-popup">
       <div class="cd-popup-container">
        <h1>
         扫描二维码,加微信公众号
        </h1>
        <img src="http://dataunion.org/wp-content/themes/yzipi/images/2014-12-06-1515289049.png"/>
        <a class="cd-popup-close" href="http://dataunion.org/16736.html">
        </a>
       </div>
       <!-- cd-popup-container -->
      </div>
      <!-- cd-popup -->
     </div>
    </div>
    <!--about-->
    <div class="bottom">
     <a href="http://dataunion.org/">
      数盟社区
     </a>
     <a href="http://www.miitbeian.gov.cn/" rel="external nofollow" target="_blank">
      京ICP备14026740号
     </a>
     联系我们：
     <a href="mailto:contact@dataunion.org" target="_blank">
      contact@dataunion.org
     </a>
     <div class="tongji">
     </div>
     <!--bottom-->
     <div class="scroll" id="scroll" style="display:none;">
      ︿
     </div>
    </div>
   </footer>
   <!--dibu-->
  </div>
 </body>
</html>